1. Field of the Invention
The present invention relates generally to data communication techniques and more particularly to new data compression techniques for use in improving the efficiency of data transmission.
2. Discussion of the Prior Art
Numerous techniques and systems have been developed heretofore for improving the efficiency of data storage or transmission of data between remote points. Notable among such systems are those which represent "characters" (letters, numerals, symbols) by codes, such as that developed by the American Standards Code For Information Interchange (ASCII), which generally are of equal length to all characters. In a character based data communications environment, however, not all possible characters appear with equal frequency. It is therefore inefficient to assign codes of equal length to all characters (like ASCII codes) in such an environment. A communications processor cannot in general known ahead of time what the frequency distribution of characters to be transmitted will be. It cannot make a preliminary pass through a data stream in order to determine the frequency distribution by which to assign codes. Moreover, since it must be ready to transmit the code or a particular character with minimal delay, this rules out the possibility of allowing the processor to accumulate data and encode it before beginning transmission. Therefore, in order to be highly efficient, a compression technique for use in a data communications environment must be predictive and adaptive. It should be able to predict the best code assignments for all possible characters based upon the distribution of characters which have already been transmitted. It should be able to detect changes in the frequency distribution of characters in a data stream and adapt its coding scheme accordingly. Furthermore, these functions must be accomplished with minimal down loading of coding information to the receiving processor which must decode the encoded transmission. The technique should be simple enough that it can be implemented on a eight bit microprocessor and it must work with sufficient speed that it can operate in a real time data communications environment.
It has been proposed, therefore, to compress character based and like data by one of two basic techniques. The first is known as "run length coding" as exemplified by the U.S. Pat. Nos. 4,124,870, issued Nov. 7, 1978, to B. R. Shatz, et al and 4,150,400, issued Apr. 17, 1979, to K. Y. Wong, while the latter is known in the art as the delta encoding technique as exemplified by U.S. Pat. No. 3,524,926, issued Aug. 18, 19790 to A. T. Starr, et al. Another example of data bit compression in conjunction with the facsimile transmission of alphanumeric characters can be found in U.S. Pat. No. 4,151,562, issued Apr. 24, 1979, to J. L. Tregay, while U.S. Pat. No. 4,131,915, issued Dec. 26, 1978, to Y, Nakagome, et al, discloses a facsimile signal transmission system which uses dummy codes to increase the number of bits of variable length codes to make the codes longer than a reference bit number predetermined in consideration of the subscanning time at the receiving side of the system.
It is also known in digital message transmission systems in which an analog speech or video signal is converted to a digital pulse train by a technique known as differential pulse code modulation (DPCM). This technique periodically samples the incoming signal and quantize the difference between each pulse sample and a prediction of it based on past samples' values prior to coding the pulse train for transmission. Examples of this technique can be found in U.S. Pat. Nos. 3,772,682, issued Nov. 13, 1973, to J. L. Flanagan, 3,931,596, issued Jan. 6, 1976, to A. Gersho, and 4,206,447, issued June 3, 1980, to Y. W. Ching, et al.